# Definition for a binary tree node.
class TreeNode:
    id_ = 0
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.id = TreeNode.id_
        TreeNode.id_ += 1
    def __repr__(self):
        return str(self.id)

class Solution:
    def closeLampInTree(self, root: TreeNode) -> int:
        cache = {}
        def set_subtree(u, s1, s2):
            if (u, s1, s2) in cache:
                return cache[(u, s1, s2)]
            children = [v for v in [u.left, u.right] if v]
            n1 = sum([set_subtree(v, s2, s2) for v in children]) + int(u.val != s1)
            n2 = sum([set_subtree(v, 1 - s2, s2) for v in children]) + int(u.val != 1 - s1) + 1
            n3 = sum([set_subtree(v, 1 - s2, 1 - s2) for v in children]) + int(u.val != 1 - s1) + 1
            n4 = sum([set_subtree(v, s2, 1 - s2) for v in children]) + int(u.val != s1) + 2
            result = min(n1, n2, n3, n4)
            cache[(u, s1, s2)] = result
            return result
        result = set_subtree(root, 0, 0)
        return result


def lst2tree(lst):
    if not lst:
        return None

    parents = {}
    root = TreeNode(lst[0])
    layer_nodes = [root]
    lst = lst[1:]
    while lst:
        pop_cnt = min(len(layer_nodes) * 2, len(lst))
        popped, lst = lst[:pop_cnt], lst[pop_cnt:]
        new_layer_nodes = []
        for i, x in enumerate(popped):
            if x is not None:
                node = TreeNode(x)
                parents[node] = (layer_nodes[i // 2], i % 2 == 0)
                new_layer_nodes.append(node)
        layer_nodes = new_layer_nodes
    for v, (u, is_left) in parents.items():
        if is_left:
            u.left = v
        else:
            u.right = v
    return root


null = None
def get_size(root):
    def dfs(u):
        if u is None:
            return 0
        return dfs(u.left) + dfs(u.right) + 1
    return dfs(root)

n = null

root = lst2tree([1, 0, 1,1,1, 0, n, n,1])
print('size:', get_size(root))
res = Solution().closeLampInTree(root)
print('result:', res)


# root = lst2tree([1,n, 1, n, n, 0, 0, n,n,n,n,1,n,n,n, n,n,n,n,n,n,n,n,0])
# print('size:', get_size(root))
# res = Solution().closeLampInTree(root)
# print('result:', res)
#
# root = lst2tree([1,null,1,0,0,1,null,null,null,0])
# print('size:', get_size(root))
# res = Solution().closeLampInTree(root)
# print(res)

# root = lst2tree([1,1,0,null,null,null,1])
# res = Solution().closeLampInTree(root)
# print(res)
#
# root = lst2tree([1,1,1,1,null,null,1])
# res = Solution().closeLampInTree(root)
# print(res)
